|
The Held–Karp algorithm, also called Bellman–Held–Karp algorithm, is a dynamic programming algorithm proposed in 1962 independently by Bellman〔‘Dynamic programming treatment of the travelling salesman problem’, Richard Bellman, ''Journal of Assoc. Computing Mach.'' 9. 1962.〕 and by Held and Karp〔'A dynamic programming approach to sequencing problems’, Michael Held and Richard M. Karp, ''Journal for the Society for Industrial and Applied Mathematics'' 1:10. 1962〕 to solve the Traveling Salesman Problem (TSP). TSP is an extension of the Hamiltonian circuit problem. The problem can be described as: find a tour of N cities in a country (assuming all cities to be visited are reachable), the tour should (a) visit every city just once, (b) return to the starting point and (c) be of minimum distance.〔http://www.cs.man.ac.uk/~david/algorithms/graphs.pdf〕 Broadly, the TSP is classified as symmetric travelling salesman problem (sTSP), asymmetric travelling salesman problem (aTSP), and multi-travelling salesman problem (mTSP).The mTSP is generally treated as a relaxed vehicle routing problem. ==Graph model== sTSP: Let ''V'' = be a set of cities, ''E'' = be the edge set, and ''d''''rs'' = ''d''''s''r be a cost measure associated with edge ( ''r'', ''s'' ) ∈ ''E''. aTSP: If ''d''''rs'' ≠ ''d''''sr'' for at least one ( ''r'', ''s'' ) then the sTSP becomes an aTSP. The aTSP and sTSP are defined on different graphs – complete directed and undirected. sTSP can be considered, in many cases, as a subproblem of the aTSP. mTSP: The mTSP is defined as: In a given set of nodes, let there are m salesmen located at a single depot node. The remaining nodes (cities) that are to be visited are intermediate nodes. Then, the mTSP consists of finding tours for all m salesmen, who all start and end at the depot, such that each intermediate node is visited exactly once and the total cost of visiting all nodes is minimized. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Held–Karp algorithm」の詳細全文を読む スポンサード リンク
|